﻿//给你一个链表数组，每个链表都已经按升序排列。
//请你将所有链表合并到一个升序链表中，返回合并后的链表。
//
//输入：lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
//输出：[1, 1, 2, 3, 4, 4, 5, 6]
//解释：链表数组如下：
//[
//	1->4->5,
//		1->3->4,
//		2->6
//]
//将它们合并到一个有序链表中得到。
//1->1->2->3->4->4->5->6
//
//输入：lists = []
//输出：[]
//
//输入：lists = [[]]
//输出：[]
//
//提示：
//	k == lists.length
//	0 <= k <= 10 ^ 4
//	0 <= lists[i].length <= 500
//	- 10 ^ 4 <= lists[i][j] <= 10 ^ 4
//	lists[i] 按 升序 排列
//	lists[i].length 的总和不超过 10 ^ 4

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
    struct cmp {
        bool operator()(const ListNode* l1, const ListNode* l2) {
            return l1->val > l2->val;
        }
    };

public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 创建⼀个⼩根堆

        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
        // 让所有的头结点进⼊⼩根堆

        for (auto l : lists)
            if (l)
                heap.push(l);
        // 合并k个有序链表

        ListNode* ret = new ListNode(0);
        ListNode* prev = ret;
        while (!heap.empty()) {
            ListNode* t = heap.top();
            heap.pop();
            prev->next = t;
            prev = t;
            if (t->next)
                heap.push(t->next);
        }
        prev = ret->next;
        delete ret;
        return prev;
    }
};